'''
https://leetcode.cn/problems/longest-palindromic-substring/description/
'''


class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '#' + '#'.join(s) + '#'
        n = len(s)
        p = [1] * n
        i, center, r = 0, 0, 0
        while i < n:
            i_prime = 2 * center - i
            radius = min(p[i_prime], r - i) if r > i else 1
            while 0 <= i - radius and i + radius < n and s[i - radius] == s[i + radius]:
                radius += 1
            if i + radius > r:
                center, r = i, i + radius
            p[i] = radius
            i += 1
        max_radius, mid = max((radius, i) for i, radius in enumerate(p))  # 相对s
        start, end = mid - max_radius + 2, mid + max_radius - 1
        return s[start: end: 2]

    def longestPalindrome2(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        start = 0
        res = 1
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                start = i
                res = 2
        for i in range(n - 2, -1, -1):
            for j in range(i + 2, n):
                dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
                if dp[i][j] and j - i + 1 > res:
                    start = i
                    res = j - i + 1
        return s[start: start+res]


# word = 'ccc'
# word = 'babad'
# word = 'cbbd'
word = 'abacab'
print(Solution().longestPalindrome2(word))
